V polovině 13. století při založení královského města Kolín byl zřejmě založen i kostel, z něhož se chrám vyvinul do současné podoby. Zakladatelem byl nejspíše král Přemysl Otakar II. Stavba byla dokončena před rokem 1300 vybudováním dvou štíhlých osmibokých věží na západním průčelí.
Za vlády Karla IV. prodělo město Kolín požár, během kterého byl poškozen také kostel, který následně prošel přestavbou. Petr Parléř tehdy v letech 1360 - 1379 vybudoval nový gotický chór, byla rozšířena okna v trojlodí a proběhla také přístavba kaple Panny Marie. Petr Parléř tedy v Kolíně zahájil výstavbu nového, vysokého chóru na místě původního presbytáře. Obnovený chrám byl vysvěcen roku 1378. Vlastní kostel je trojlodní stavba, postavená v gotickém slohu. Nižší, západní část je raně gotická s vnějším opěrným systémem. Na severní straně se nacházejí dva vstupní portály. Tympanon pravého portálu je kopií původní plastiky ze 13. století, která byla sňata při rekonstrukci na konci 19. století.
Ke konci 15. století byly západní věže opatřeny věžemi ve tvaru jehlanu a nárožní věžičky. Roku 1643 kostel rabovala švédská vojska a značně jej poškodila. Další pohroma měla podobu požáru, který kostel poškodil roku 1976. Generální rekonstrukce pak proběhla v polovině 19. století, jenomže záhy, roku 1869, přišel další ničivý požár. Další rekonstrukce je vedena Josefem Mockerem, který nejdříve přestavil severní věž a zvonici, poté rekonstruuje i Parléřovu práci - chór, kde řadu architektonických prvků buď doplnil a nebo zcela vyměnil. Zastřešení katedrály také pochází z 19. století.